package cyc2018.双指针;

import java.util.List;

/**
 * 通过删除字母匹配到字典里最长单词
 *
 * 删除 s 中的一些字符，使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。
 * 如果有多个相同长度的结果，返回字典序的最小字符串。
 *
 * 示例 1:
 *
 * 输入:
 * s = "abpcplea", d = ["ale","apple","monkey","plea"]
 *
 * 输出:
 * "apple"
 */
public class Test524 {

    public String findLongestWord(String s, List<String> d) {
        String longestWord = "";
        // 取出字典里面的数据，与当前的字符串比较
        for (String target : d) {
            int l1 = longestWord.length(), l2 = target.length();
            if (l1 > l2 || (l1 == l2 && longestWord.compareTo(target) < 0)) {
                continue;
            }
            if (isValid(s, target)) {
                longestWord = target;
            }
        }
        // 要么返回最长的字典字符串、要么返回 “ ”
        return longestWord;
    }

    // 判断 s 经过删除后能否等于 target
    private boolean isValid(String s, String target) {
        int i = 0, j = 0;
        while (i < s.length() && j < target.length()) {
            // 如果 s 的某个字符与 target 不一致，则删除s的当前字符，判断下一个是否与target当前字符一致。直到结束
            if (s.charAt(i) == target.charAt(j)) {
                j++;
            }
            i++;
        }
        // s 能修改成 target的条件就是 j 走到 target 头
        return j == target.length();
    }
}
